CS3501 Complier Design Syllabus - Anna University

CS3501 COMPILER DESIGN

L T P C: 3 0 2 4

COURSE OBJECTIVES:

• To learn the various phases of compiler.
• To learn the various parsing techniques.
• To understand intermediate code generation and run-time environment.
• To learn to implement the front-end of the compiler.
• To learn to implement code generator.
• To learn to implement code optimization.

UNIT I INTRODUCTION TO COMPILERS & LEXICAL ANALYSIS

Introduction- Translators- Compilation and Interpretation- Language processors -The Phases of Compiler - Lexical Analysis - Role of Lexical Analyzer - Input Buffering - Specification of Tokens - Recognition of Tokens - Finite Automata - Regular Expressions to Automata NFA, DFA - Minimizing DFA - Language for Specifying Lexical Analyzers - Lex tool.

UNIT II SYNTAX ANALYSIS

Role of Parser - Grammars - Context-free grammars - Writing a grammar Top Down Parsing - General Strategies - Recursive Descent Parser Predictive Parser-LL(1) - Parser-Shift Reduce Parser-LR Parser- LR (0)Item Construction of SLR Parsing Table - Introduction to LALR Parser - Error Handling and Recovery in Syntax Analyzer-YACC tool - Design of a syntax Analyzer for a Sample Language

UNIT III SYNTAX DIRECTED TRANSLATION & INTERMEDIATE CODE GENERATION

Syntax directed Definitions-Construction of Syntax Tree-Bottom-up Evaluation of S-Attribute Definitions- Design of predictive translator - Type Systems-Specification of a simple type Checker- Equivalence of Type Expressions-Type Conversions. Intermediate Languages: Syntax Tree, Three Address Code, Types and Declarations, Translation of Expressions, Type Checking, Back patching.

UNIT IV RUN-TIME ENVIRONMENT AND CODE GENERATION

Runtime Environments - source language issues - Storage organization - Storage Allocation Strategies: Static, Stack and Heap allocation - Parameter Passing-Symbol Tables - Dynamic Storage Allocation - Issues in the Design of a code generator - Basic Blocks and Flow graphs - Design of a simple Code Generator - Optimal Code Generation for Expressions- Dynamic Programming Code Generation.

UNIT V CODE OPTIMIZATION

Principal Sources of Optimization - Peep-hole optimization - DAG- Optimization of Basic Blocks - Global Data Flow Analysis - Efficient Data Flow Algorithm - Recent trends in Compiler Design.

45 PERIODS

LIST OF EXPERIMENTS:

1. Using the LEX tool, Develop a lexical analyzer to recognize a few patterns in C. (Ex. identifiers, constants, comments, operators etc.). Create a symbol table, while recognizing identifiers.
2. Implement a Lexical Analyzer using LEX Tool
3. Generate YACC specification for a few syntactic categories.
   a. Program to recognize a valid arithmetic expression that uses operator +, -, * and /.
   b. Program to recognize a valid variable which starts with a letter followed by any number of letters or digits.
   c. Program to recognize a valid control structures syntax of C language (For loop, while loop, if-else, if-else-if, switch-case, etc.).
   d. Implementation of calculator using LEX and YACC
4. Generate three address code for a simple program using LEX and YACC.
5. Implement type checking using Lex and Yacc.
6. Implement simple code optimization techniques (Constant folding, Strength reduction and Algebraic transformation)
7. Implement back-end of the compiler for which the three address code is given as input and the 8086 assembly language code is produced as output.

30 PERIODS

TOTAL: 75 PERIODS

COURSE OUTCOMES:

On Completion of the course, the students should be able to:

• CO1:Understand the techniques in different phases of a compiler.
• CO2:Design a lexical analyser for a sample language and learn to use the LEX tool.
• CO3:Apply different parsing algorithms to develop a parser and learn to use YACC tool
• CO4:Understand semantics rules (SDT), intermediate code generation and run-time environment.
• CO5:Implement code generation and apply code optimization techniques.

TEXT BOOK:

1. Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman, "Compilers: Principles, Techniques and Tools", Second Edition, Pearson Education, 2009.

REFERENCES

1. Randy Allen, Ken Kennedy, Optimizing Compilers for Modern Architectures: A Dependence based Approach, Morgan Kaufmann Publishers, 2002.
2. Steven S. Muchnick, Advanced Compiler Design and Implementation, Morgan Kaufmann Publishers - Elsevier Science, India, Indian Reprint 2003.
3. Keith D Cooper and Linda Torczon, Engineering a Compiler, Morgan Kaufmann Publishers Elsevier Science, 2004.
4. V. Raghavan, Principles of Compiler Design, Tata McGraw Hill Education Publishers, 2010.
5. Allen I. Holub, Compiler Design in C, Prentice-Hall Software Series, 1993.